package com.mdnote.practice.dfs_bfs;

import com.mdnote.practice.generic_recursion.LeetCode297;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/17
 * @description 在每个树行中找最大值
 */
public class LeetCode515 {


    public static void main(String[] args) {
        LeetCode515 leetCode515 = new LeetCode515();
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(5);
        root.right = new TreeNode(15);
        root.left.left = new TreeNode(2);
        List<Integer> resList = leetCode515.largestValues(root);

        System.out.println(resList);

    }
    public List<Integer> largestValues(TreeNode root) {

        if (root == null) {
            return new ArrayList<>();
        }
        // BFS
//       List<Integer> resList =  bfs(root);

        // DFS
        ArrayList<Integer> resList = new ArrayList<>();
        dfs(root, 0, resList);
        return resList;
    }

    private void dfs(TreeNode node, int level, List<Integer> resList) {
        if (node == null) {
            return;
        }

        if (resList.size() < level + 1) {
            resList.add(Integer.MIN_VALUE);
        }
        Integer max = resList.get(level);
        if (node.val > max) {
            resList.set(level, node.val);
        }

        if (node.left != null) {
            dfs(node.left, level + 1, resList);
        }
        if (node.right != null) {
            dfs(node.right, level + 1, resList);
        }
    }

    private List<Integer> bfs(TreeNode node) {

        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(node);

        ArrayList<Integer> resList = new ArrayList<>();
        int level = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < size; i++) {
                TreeNode tempNode = queue.removeFirst();
                // current logic

                if (tempNode.val > max) {
                    max = tempNode.val;
                }
                
                if (tempNode.left != null) {
                    queue.addLast(tempNode.left);
                }
                if (tempNode.right != null) {
                    queue.addLast(tempNode.right);
                }
            }
            resList.add(max);
            level++;
        }
        return resList;
    }


    private static class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode() {}
         TreeNode(int val) { this.val = val; }
         TreeNode(int val, TreeNode left, TreeNode right) {
             this.val = val;
             this.left = left;
             this.right = right;
         }
     }

}
